| 求出最大连续子序列和 暴力算法、分治法、动态规划、贪心算法实现;Leecode 51.最大子序和 | 您所在的位置：网站首页 › 最大连续子序列 动态规划 › 求出最大连续子序列和 暴力算法、分治法、动态规划、贪心算法实现;Leecode 51.最大子序和 |
求出最大连续子序列和 暴力算法、分治法、动态规划、贪心算法实现;Leecode 51.最大子序和
|
求出最大连续子序列和
【问题描述】 给定一个整数数组 a[ ] ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 这个问题也可转入Leecode 51.最大子序和 来源：力扣（LeetCode） 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 以下用四种方法实现 ①蛮力法（即暴力算法）实现： 算法复杂度T(n)=O(n^3) 解法2： 改进前面的解法，在求两个相邻子序列和的时候，它们之间是关联的。 例如a[0…3]子序列和=a[0]+a[1]+a[2]+a[3],a[0…4]子序列和=a[0]+a[1]+a[2]+a[3]+a[4] 在前者计算出来后，求后者时只需在前者的基础上加上a[4]即可，没有必须每次都重复计算。 从而提高算法效率。 代码实现： int maxSbuSum2(int a[],int n) { int i,j; int maxSum=0,thisSum; for(i=0;i thisSum+=a[i]; if(thisSum>maxSum) maxSum=thisSum; } } return maxSum; }时间复杂度T(n)=O(n^2) 解法3：更进一步改进解法2 如果扫描中遇到了负数，当前子序列和thisSum将会减小，若thisSum为负数，表明 前面已经扫描的那个子序列可以抛弃了，则放弃这个子序列，重新开始下一个子序 列的分析，并置thisSum为0 若这个子序列和thisSum不断增加，那么最大子序列和maxSumy也不断增加。 int maxSubSum(int a[],int n){ int j,maxSum=0,thisSum=0; for(j=0;j0,-2,11,-4,13,-5,-2}; int max(long a,long b,long c){ //求出a,b,c三者中的最大值 if(ac) return a; else return c; } int maxSubArray(int left,int right) { int i,j; int maxLeftSum,maxRightSum; int maxLeftBorderSum,leftBorderSum; int maxRightBorderSum,rightBorderSum; if(left==right){ //当子序列只有一个元素时 if(a[left]>0) //元素大于0的时候返回它 return a[left]; else return 0; //小于或等于0的时候返回0 } int mid=(left+right)/2; maxLeftSum=maxSubArray(left,mid); //求左边的最大连续子序列的和 maxRightSum=maxSubArray(mid+1,right); //求右边的最大连续子序列之和 maxLeftBorderSum=0,leftBorderSum=0; for(i=mid;i>=left;i--){ //求出以左边加上a[mid]元素构成的序列的最大和 leftBorderSum+=a[i]; if(leftBorderSum>maxLeftBorderSum) maxLeftBorderSum=leftBorderSum; } maxRightBorderSum=0,rightBorderSum=0; for(j=mid+1;j printf("%d",maxSubArray(0,n)); return 0; }③动态规划算法实现： dp[i]表示数组a中以a[i]结尾的最大子序列和 状态转移方程如下 dp[0]=0 （边界条件） dp[i]=max{dp[i-1]+ai,ai} (1 int result=INT_MIN; dp[0]=0; result=dp[0]; for(int j=1;j cout //因为int占4字节32位，根据二进制编码的规则，INT_MAX = 2^31-1，INT_MIN= -2^31. //C/C++中，所有超过该限值的数，都会出现溢出，出现warning，但是并不会出现error //INT_MAX = 2^31 - 1 =2147483647，INT_MIN= - 2^31 = -2147483648 int result = INT_MIN; int sum = 0; for (int i = 0; i sum = 0; } } return result; } int main(){ cout |
代码实现：【本文地址】